package src.dual_pointers;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author starsea
 * @date 2024-08-25 19:18
 */

public class Test08 {
    public static void main(String[] args) {
        String  s = "baa";
        String p = "aa";
        List list=findAnagrams(s,p);
    }
    public static List<Integer> findAnagrams(String s, String p) {
        if(s.length()<p.length())
        {
            return new ArrayList<>();
        }
        List<Integer> ret=new ArrayList<>();
        Map<Character,Integer> Smap=new HashMap<>();
        Map<Character,Integer>Pmap=new HashMap<>();
        for(int i=0;i<p.length();i++)
        {
            if(Pmap.containsKey(p.charAt(i)))
            {
                Pmap.put(p.charAt(i),Pmap.get(p.charAt(i))+1);
            }else {
                Pmap.put(p.charAt(i),1);
            }
            if(Smap.containsKey(s.charAt(i)))
            {
                Smap.put(s.charAt(i),Smap.get(s.charAt(i))+1);
            }else {
                Smap.put(s.charAt(i),1);
            }
        }
        int left=0;
        int right=p.length()-1;
        while(right<s.length())
        {
            if(Smap.equals(Pmap))
            {
                ret.add(left);
            }
            if(Smap.get(s.charAt(left))==1)
            {
                Smap.remove(s.charAt(left));
            }else
            {
                Smap.put(s.charAt(left),Smap.get(s.charAt(left))-1);
            }
            left++;
            right++;
            if(right>=s.length())
            {
                break;
            }
            if(Smap.containsKey(s.charAt(right)))
            {
                Smap.put(s.charAt(right),Smap.get(s.charAt(right))+1);
            }else
            {
                Smap.put(s.charAt(right),1);
            }
        }
        return  ret;
    }
}
